package leetcode.N1301_N1400;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;

/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/11/6 11:28 上午
 */
public class N1356 {

    public static void main(String[] args) {
        int[] arr = {1024,512,256,128,64,32,16,8,4,2,1};
        N1356 s = new N1356();
        s.sortByBits(arr);
    }


    /**
     * 题设中规定 arr[i] < 10000  1 << 14 = 16384  所以可知 对于每一个arr[i] 其二进制数中包含1的个数最多有14个
     * 1.构建一个包含15个桶的数组  根据元素包含「1」的个数进行分装
     * 2.每一个桶中根据元素值进行排序
     * 3.最终依次遍历所有的桶中元素，将其合并
     *
     * @param arr
     * @return
     */
    public int[] sortByBits(int[] arr) {
        // 输入检测
        int length;
        if (arr == null || (length = arr.length) == 0) {
            return arr;
        }
        ArrayList<Integer>[] buckets = new ArrayList[15];
        for (int val : arr) {
            // 计算二进制数中包含「1」的个数
            int index = count(val);
            // 存入元素到对应的桶中
            getBucket(index, buckets).add(val);
        }

        int currentIndex = 0;
        // 遍历存放元素 新数组
        int[] newArray = new int[length];
        for (ArrayList<Integer> bucket : buckets) {
            if (bucket == null || bucket.size() == 0) {
                continue;
            }
            Collections.sort(bucket);
            for (Integer i : bucket) {
                newArray[currentIndex++] = i;
            }
        }
        return newArray;
    }

    public ArrayList<Integer> getBucket(int index, ArrayList<Integer>[] buckets) {
        ArrayList<Integer> bucket = buckets[index];
        if (bucket != null) {
            return bucket;
        }
        bucket = new ArrayList<>();
        buckets[index] = bucket;
        return bucket;
    }

    public int count(int value) {
        int count = 0;
        while (value > 0) {
            value = value & (value - 1);
            count++;
        }
        return count;
    }

}